public class AVL
{
    private NodoAVL root;
    
    public AVL()
    {
        this.root = null;
    }
    
    public void insert(int value)
    {
        NodoAVL nuevo = new NodoAVL(value);
        this.root = insert(this.root, nuevo);
    }
    
    private NodoAVL insert(NodoAVL p, NodoAVL q)
    {
        if(p == null)
        {
            return q;
        }
        else if(q.key<p.key)
        {   
            p.left = insert(p.left,q);
        }
        else
        {
            p.right = insert(p.right,q);
        }
        
        p = isBalanced(p);
        return p;
    }
    
    public void imprimir()
    {
        this.imprimir(this.root);
    }
            
    private void imprimir(NodoAVL root)
    {
        if(root!=null)
        {
            System.out.print(" "+root.key);
            imprimir(root.left);  
            imprimir(root.right);
        }
    }
    
    private int height(NodoAVL p)
    {
        if(p==null)
        {
            return -1;
        }
        if(p.left==null && p.right==null) {
            return 0;
        }
        else if(p.left==null)
        {
            return 1+height(p.right);
        } 
        else if(p.right==null)
        {
            return 1+height(p.left);
        } 
        else 
        {
            return 1+Math.max(height(p.left),height(p.right));
        }
    }
    
    private int getBalanced(NodoAVL p)
    {
        return height(p.left)- height(p.right);
    }

    private NodoAVL isBalanced(NodoAVL p)
    {
        int balance = getBalanced(p);
        
        if(balance==-2)
        {
            if(getBalanced(p.right) == -1)
            {
                if(Hashing.verbosa)
                {
                    System.out.println("Rotación simple a la izquierda");
                }
                p = singleLeftRotation(p);
            }
            else
            {
                if(Hashing.verbosa)
                {
                    System.out.println("Rotación doble Derecha-Izquierda");
                }
                p = rightLeftRotation(p);
            }
        }
        else if(balance==2)
        {
            if(getBalanced(p.left) == 1)
            {
                if(Hashing.verbosa)
                {
                    System.out.println("Rotación simple a la derecha");
                }
                p = singleRightRotation(p);
            }
            else
            {
                if(Hashing.verbosa)
                {
                    System.out.println("Rotación doble Izquierda-Derecha");
                }
                p = leftRightRotation(p);
            }
        }
        
        return p;
    }
    
    
    private NodoAVL singleLeftRotation(NodoAVL p)
    {
        NodoAVL aux = p.right;
        p.right = aux.left;
        aux.left = p;
        return aux;
    }
    
    private NodoAVL singleRightRotation(NodoAVL p)
    {
        NodoAVL aux = p.left;
        p.left = aux.right;
        aux.right = p;
        return aux;
    }
    
    private NodoAVL rightLeftRotation(NodoAVL p)
    {
        p.right = singleRightRotation(p.right);
        p = singleLeftRotation(p);
        return p;
    }
    
    private NodoAVL leftRightRotation(NodoAVL p)
    {
        p.left = singleLeftRotation(p.left);
        p = singleRightRotation(p);
        return p;
    }
    
    public boolean search(int key)
    {
        return search(root, key);
    }
    
    private boolean search(NodoAVL root, int key)
    {
        if(root == null) {
            Hashing.comparaciones++;
            return false;
        }
        if(root.key == key) {
            Hashing.comparaciones++;
            return true;
        }
        else if(key < root.key) {
            Hashing.comparaciones++;
            return search(root.left, key);
        }
        else {
            Hashing.comparaciones++;
            return search(root.right, key);
        }
    }
}

class NodoAVL
{
    public int key;
    public NodoAVL left;
    public NodoAVL right;

    public NodoAVL(int key)
    {
        this.key = key;
        this.left = null;
        this.right = null;
    }   
}